Löwenheim-Skolem Theorem
The Löwenheim-Skolem Theorem says that if M'' is an infinite model in some language ''L, then for every cardinal \kappa \ge |L| , there is a model N'' of cardinality \kappa , elementarily equivalent to ''M. More precisely, one has two theorems: Downward Löwenheim-Skolem Theorem: Let M'' be an infinite model in some language ''L. Then for any subset S ⊆ M, there exists an elementary substructure N \preceq M containing S'', with |N| = |S| + |L| . In particular, taking ''S to be an arbitrary subset of size \kappa with |L| \le \kappa \le |M| , we can find an elementary substructure of M'' of size \kappa . '''Upward Löwenheim-Skolem Theorem': Let M'' be an infinite model in some language ''L. Then for every cardinal \kappa bigger than |''M''| and |''L''|, there is an elementary extension of M'' of size \kappa . On the level of theories, the Löwenheim-Skolem Theorem implies that if ''T is a theory with an infinite model, then T'' has a model of cardinality \kappa for every infinite \kappa \ge |T| . These statements become slightly simpler when working in a countable language. In this case, Upward Löwenheim-Skolem says that if ''M is an infinite structure, then M'' has elementary extensions of all cardinalities greater than |''M|. Similarly, Downward Löwenheim-Skolem implies that if M'' is an infinite structure, then ''M has elementary substructures of all infinite sizes less than |''M''|. Proof of Downward Löwenheim-Skolem Theorem Let M'' be a structure. For each non-empty definable subset ''D of M'', choose some element ''e(D) ∈ D, using the axiom of choice. If X'' is any subset of ''M, let : c(X) = X \cup \{e(D) : D \text{ definable over }X,~ D \ne \emptyset \} Note that over a set of size \lambda , there are at most \lambda + |L| definable sets. Consequently, : |c(X)| \le |X| + |L| Now given S ⊆ M as in the theorem, let : N = S \cup c(S) \cup c(c(S)) \cup \cdots By basic cardinal arithmetic, |N| = |S| + |L| . Then N \preceq M by the Tarski-Vaught test. Indeed, if D'' is a subset of ''M definable over N'', then ''D uses only finitely many parameters, and is therefore definable over c(i)(S) ⊆ N for some i''. Then : e(D) \in c^{(i+1)}(S) \subset N , so ''e(D) is an element of N \cap D . Therefore, every non-empty N''-definable set intersects ''N. Therefore the Tarski-Vaught criterion holds and N'' is an elementary substructure of ''M. It has the correct size. QED Proof of Upward Löwenheim-Skolem Theorem Given an infinite structure M'' and a cardinal \kappa at least as big as both |''M| and |''L''|, let T'' be the union of the elementary diagram of ''M and the collection of statements : \{c_\alpha \ne c_\beta : \alpha < \beta < \kappa \} where \{c_\alpha\}_{\alpha < \kappa} is a collection of \kappa new constant symbols. By compactness, T'' is consistent. Indeed, any finite subset of ''T only mentions finitely many of the c_\alpha and therefore has a model consisting of M'' with the finitely many c_\alpha interpreted as distinct elements of ''M. So by compactness we can find a model N \models T . Then N'' is a model of the elementary diagram of ''M, so N'' is an elementary extension of ''M. Also, the c_\alpha ensure that N'' contains at least \kappa distinct elements, i.e., |N| \ge \kappa . There is a possiblity that ''N is too big; to hit \kappa on the nose, we use Downward Löwenheim-Skolem to find an elementary substructure of N'' having size \kappa and containing ''M. On general grounds, the resulting structure is an elementary extension of M. QED